package com.easy.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

//56. 合并区间
public class Merge56 {
    public int[][] merge(int[][] intervals) {
        //Arrays.stream(intervals).sorted((val1,val2)->val1[0]-val2[0]);
        //int[][] res= new int[intervals.length][2];
        //Arrays.stream(intervals).sorted((val1,val2)->val1[0]-val2[0]).collect(Collectors.toList()).toArray(res);
        //排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        //存放结果
        List<int[]> res= new ArrayList<>();
        //遍历数组
        for (int i = 0; i < intervals.length; i++) {
            //最小值
            int start= intervals[i][0];
            //最大值
            int end=intervals[i][1];
            //下一个值的开始值，小于当前的最大值，说明这两个是连续区间，继续
            while (i+1<intervals.length&&end>=intervals[i+1][0]){
                //最小值
                start =Math.min(start,intervals[i+1][0]);
                //最大值
                end =Math.max(end,intervals[i+1][1]);
                i++;
            }
            //记录连续区间的开始与结束
            res.add(new int[]{start,end});
        }
        return res.toArray(new int[res.size()][2]);
    }

    public static void main(String[] args) {
        Merge56 merge56 = new Merge56();
        merge56.merge(new int[][]{{2,3},{4,5},{6,7},{8,9},{1,10}});
    }
}
